class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}
public class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null)
            return true;
        if (root.left == null && root.right == null)
            return true;
        boolean leftTree = isValidBST(root.left);
        boolean rightTree = isValidBST(root.right);
        if (root.left != null && root.left.val >= root.val)
            return false;
        if (root.right != null && root.right.val <= root.val)
            return false;
        return leftTree && rightTree && findLeftTreeMax(root.left, root.val) && findRightTreeMin(root.right, root.val);
    }
    private boolean findLeftTreeMax(TreeNode cur, int val) {
        if(cur == null) return true;
        while(cur.right != null) {
            cur = cur.right;
        }
        if(cur.val < val) return true;
        return false;
    }
    private boolean findRightTreeMin(TreeNode cur, int val) {
        if(cur == null) return true;
        while(cur.left != null) {
            cur = cur.left;
        }
        if(cur.val > val) return true;
        return false;
    }
    public int rob(int[] nums) {
        int n = nums.length;
        if(n == 1) return nums[0];//处理边界情况
        int[] f1 = new int[n-1];
        int[] g1 = new int[n-1];
        f1[0] = nums[0];
        for(int i = 1; i < n-1; i++) {
            f1[i] = g1[i-1] + nums[i];
            g1[i] = Math.max(f1[i-1], g1[i-1]);
        }
        int max1 = Math.max(f1[n-2], g1[n-2]);

        int[] f2 = new int[n-1];
        int[] g2 = new int[n-1];
        f2[0] = nums[1];
        for(int i = 1; i < n-1; i++) {
            f2[i] = g2[i-1] + nums[i+1];
            g2[i] = Math.max(f2[i-1], g2[i-1]);
        }
        int max2 = Math.max(f2[n-2], g2[n-2]);
        return Math.max(max1, max2);
    }
}